package class_0826HashTable;

import java.util.HashMap;

/**
 * 0. 回顾哈希映射，哈希碰撞（冲突）
 * 1. 哈希函数设计原理
 * 2. 一致性哈希原理
 * 3.
 * @author 90774
 */
public class Coding_HashTable {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /**
     * 简单题----只出现一次的数字。
     */
    public static int singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int x: nums){
            map.put(x,map.getOrDefault(x,0)+1);
        }
        for(int x: nums){
            int val = map.get(x);
            if(val==1){
                return x;
            }
        }
        return 0;
    }
    /**
     * 随机指针链表的复制
     */
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        HashMap<Node,Node> map = new HashMap<>();
        for(Node cur = head;cur!=null;cur=cur.next){
            Node node = new Node(cur.val);
            map.put(cur,node);
        }
        Node cur = head;
        head = map.get(cur);
        while(cur!=null){
            Node tmp = map.get(cur);
            tmp.next = map.get(cur.next);
            tmp.random = map.get(cur.random);
            cur = cur.next;
        }
        return head;
    }
    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;
        }

        Node cur = head;

        // Step 1: 扩容链表，在每个节点后面插入其拷贝节点
        while (cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }

        // Step 2: 复制 random 指针
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // Step 3: 分离出新链表，并复原原始链表
        cur = head;
        Node newHead = head.next;
        Node newCur = newHead;

        while (cur != null) {
            cur.next = cur.next.next;
            if (newCur.next != null) {
                newCur.next = newCur.next.next;
            }
            cur = cur.next;
            newCur = newCur.next;
        }

        return newHead;
    }

}
